<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-comment">-- | Graph Coloring.</span><span>
</span><span id="line-2"></span><span class="hs-comment">--      This is a generic graph coloring library, abstracted over the type of</span><span>
</span><span id="line-3"></span><span class="hs-comment">--      the node keys, nodes and colors.</span><span>
</span><span id="line-4"></span><span class="hs-comment">--</span><span>
</span><span id="line-5"></span><span>
</span><span id="line-6"></span><span class="hs-pragma">{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}</span><span>
</span><span id="line-7"></span><span class="hs-pragma">{-# LANGUAGE ScopedTypeVariables #-}</span><span>
</span><span id="line-8"></span><span>
</span><span id="line-9"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">GHC.Data.Graph.Color</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-10"></span><span>        </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html"><span class="hs-identifier">GHC.Data.Graph.Base</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-11"></span><span>        </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Ops.html"><span class="hs-identifier">GHC.Data.Graph.Ops</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-12"></span><span>        </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Ppr.html"><span class="hs-identifier">GHC.Data.Graph.Ppr</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-13"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Color.html#colorGraph"><span class="hs-identifier">colorGraph</span></a></span><span>
</span><span id="line-14"></span><span class="hs-special">)</span><span>
</span><span id="line-15"></span><span>
</span><span id="line-16"></span><span class="hs-keyword">where</span><span>
</span><span id="line-17"></span><span>
</span><span id="line-18"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Prelude.html"><span class="hs-identifier">GHC.Prelude</span></a></span><span>
</span><span id="line-19"></span><span>
</span><span id="line-20"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html"><span class="hs-identifier">GHC.Data.Graph.Base</span></a></span><span>
</span><span id="line-21"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Ops.html"><span class="hs-identifier">GHC.Data.Graph.Ops</span></a></span><span>
</span><span id="line-22"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Ppr.html"><span class="hs-identifier">GHC.Data.Graph.Ppr</span></a></span><span>
</span><span id="line-23"></span><span>
</span><span id="line-24"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html"><span class="hs-identifier">GHC.Types.Unique</span></a></span><span>
</span><span id="line-25"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html"><span class="hs-identifier">GHC.Types.Unique.FM</span></a></span><span>
</span><span id="line-26"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Types.Unique.Set.html"><span class="hs-identifier">GHC.Types.Unique.Set</span></a></span><span>
</span><span id="line-27"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html"><span class="hs-identifier">GHC.Utils.Outputable</span></a></span><span>
</span><span id="line-28"></span><span>
</span><span id="line-29"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Maybe.html#"><span class="hs-identifier">Data.Maybe</span></a></span><span>
</span><span id="line-30"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.List.html#"><span class="hs-identifier">Data.List</span></a></span><span>
</span><span id="line-31"></span><span>
</span><span id="line-32"></span><span>
</span><span id="line-33"></span><span class="hs-comment">-- | Try to color a graph with this set of colors.</span><span>
</span><span id="line-34"></span><span class="hs-comment">--      Uses Chaitin's algorithm to color the graph.</span><span>
</span><span id="line-35"></span><span class="hs-comment">--      The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes</span><span>
</span><span id="line-36"></span><span class="hs-comment">--      are pushed onto a stack and removed from the graph.</span><span>
</span><span id="line-37"></span><span class="hs-comment">--      Once this process is complete the graph can be colored by removing nodes from</span><span>
</span><span id="line-38"></span><span class="hs-comment">--      the stack (ie in reverse order) and assigning them colors different to their neighbors.</span><span>
</span><span id="line-39"></span><span class="hs-comment">--</span><span>
</span><span id="line-40"></span><span class="annot"><a href="GHC.Data.Graph.Color.html#colorGraph"><span class="hs-identifier hs-type">colorGraph</span></a></span><span>
</span><span id="line-41"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-keyword">forall</span><span> </span><span id="local-6989586621680943997"><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span></span><span> </span><span id="local-6989586621680943995"><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span></span><span> </span><span id="local-6989586621680943994"><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span></span><span class="hs-operator">.</span><span>
</span><span id="line-42"></span><span>           </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span>  </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-43"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span>
</span><span id="line-44"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-45"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span>                         </span><span class="hs-comment">-- ^ whether to do iterative coalescing</span><span>
</span><span id="line-46"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span>                          </span><span class="hs-comment">-- ^ how many times we've tried to color this graph so far.</span><span>
</span><span id="line-47"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Types.Unique.Set.html#UniqSet"><span class="hs-identifier hs-type">UniqSet</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span class="hs-special">)</span><span>       </span><span class="hs-comment">-- ^ map of (node class -&gt; set of colors available for this class).</span><span>
</span><span id="line-48"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Triv"><span class="hs-identifier hs-type">Triv</span></a></span><span>   </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span>           </span><span class="hs-comment">-- ^ fn to decide whether a node is trivially colorable.</span><span>
</span><span id="line-49"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span>     </span><span class="hs-comment">-- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.</span><span>
</span><span id="line-50"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span>           </span><span class="hs-comment">-- ^ the graph to color.</span><span>
</span><span id="line-51"></span><span>
</span><span id="line-52"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943995"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943994"><span class="hs-identifier hs-type">color</span></a></span><span>          </span><span class="hs-comment">-- the colored graph.</span><span>
</span><span id="line-53"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.Set.html#UniqSet"><span class="hs-identifier hs-type">UniqSet</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span>                  </span><span class="hs-comment">-- the set of nodes that we couldn't find a color for.</span><span>
</span><span id="line-54"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="hs-special">)</span><span>                </span><span class="hs-comment">-- map of regs (r1 -&gt; r2) that were coalesced</span><span>
</span><span id="line-55"></span><span>                                        </span><span class="hs-comment">--       r1 should be replaced by r2 in the source</span><span>
</span><span id="line-56"></span><span>
</span><span id="line-57"></span><span id="colorGraph"><span class="annot"><span class="annottext">colorGraph :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Eq cls, Ord k,
 Outputable k, Outputable cls, Outputable color) =&gt;
Bool
-&gt; Int
-&gt; UniqFM cls (UniqSet color)
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; (Graph k cls color, UniqSet k, UniqFM k k)
</span><a href="GHC.Data.Graph.Color.html#colorGraph"><span class="hs-identifier hs-var hs-var">colorGraph</span></a></span></span><span> </span><span id="local-6989586621680943838"><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943838"><span class="hs-identifier hs-var">iterative</span></a></span></span><span> </span><span id="local-6989586621680943837"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621680943837"><span class="hs-identifier hs-var">spinCount</span></a></span></span><span> </span><span id="local-6989586621680943836"><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943836"><span class="hs-identifier hs-var">colors</span></a></span></span><span> </span><span id="local-6989586621680943835"><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span></span><span> </span><span id="local-6989586621680943834"><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943834"><span class="hs-identifier hs-var">spill</span></a></span></span><span> </span><span id="local-6989586621680943833"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943833"><span class="hs-identifier hs-var">graph0</span></a></span></span><span>
</span><span id="line-58"></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">let</span><span>
</span><span id="line-59"></span><span>        </span><span class="hs-comment">-- If we're not doing iterative coalescing then do an aggressive coalescing first time</span><span>
</span><span id="line-60"></span><span>        </span><span class="hs-comment">--      around and then conservative coalescing for subsequent passes.</span><span>
</span><span id="line-61"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-62"></span><span>        </span><span class="hs-comment">--      Aggressive coalescing is a quick way to get rid of many reg-reg moves. However, if</span><span>
</span><span id="line-63"></span><span>        </span><span class="hs-comment">--      there is a lot of register pressure and we do it on every round then it can make the</span><span>
</span><span id="line-64"></span><span>        </span><span class="hs-comment">--      graph less colorable and prevent the algorithm from converging in a sensible number</span><span>
</span><span id="line-65"></span><span>        </span><span class="hs-comment">--      of cycles.</span><span>
</span><span id="line-66"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-67"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680943820"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943820"><span class="hs-identifier hs-var">graph_coalesced</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943819"><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943819"><span class="hs-identifier hs-var">kksCoalesce1</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-68"></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943838"><span class="hs-identifier hs-var">iterative</span></a></span><span>
</span><span id="line-69"></span><span>                </span><span class="hs-keyword">then</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943833"><span class="hs-identifier hs-var">graph0</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-70"></span><span>                </span><span class="hs-keyword">else</span><span> </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621680943837"><span class="hs-identifier hs-var">spinCount</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span>
</span><span id="line-71"></span><span>                        </span><span class="hs-keyword">then</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
forall k cls color.
(Uniquable k, Ord k, Eq cls, Outputable k) =&gt;
Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
</span><a href="GHC.Data.Graph.Ops.html#coalesceGraph"><span class="hs-identifier hs-var">coalesceGraph</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">True</span></span><span>  </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943833"><span class="hs-identifier hs-var">graph0</span></a></span><span>
</span><span id="line-72"></span><span>                        </span><span class="hs-keyword">else</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
forall k cls color.
(Uniquable k, Ord k, Eq cls, Outputable k) =&gt;
Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
</span><a href="GHC.Data.Graph.Ops.html#coalesceGraph"><span class="hs-identifier hs-var">coalesceGraph</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943833"><span class="hs-identifier hs-var">graph0</span></a></span><span>
</span><span id="line-73"></span><span>
</span><span id="line-74"></span><span>        </span><span class="hs-comment">-- run the scanner to slurp out all the trivially colorable nodes</span><span>
</span><span id="line-75"></span><span>        </span><span class="hs-comment">--      (and do coalescing if iterative coalescing is enabled)</span><span>
</span><span id="line-76"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680943810"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943810"><span class="hs-identifier hs-var">ksTriv</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943809"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943809"><span class="hs-identifier hs-var">ksProblems</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943808"><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943808"><span class="hs-identifier hs-var">kksCoalesce2</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span class="annot"><a href="#local-6989586621680943997"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-77"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan"><span class="hs-identifier hs-var">colorScan</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943838"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943834"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943820"><span class="hs-identifier hs-var">graph_coalesced</span></a></span><span>
</span><span id="line-78"></span><span>
</span><span id="line-79"></span><span>        </span><span class="hs-comment">-- If iterative coalescing is enabled, the scanner will coalesce the graph as does its business.</span><span>
</span><span id="line-80"></span><span>        </span><span class="hs-comment">--      We need to apply all the coalescences found by the scanner to the original</span><span>
</span><span id="line-81"></span><span>        </span><span class="hs-comment">--      graph before doing assignColors.</span><span>
</span><span id="line-82"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-83"></span><span>        </span><span class="hs-comment">--      Because we've got the whole, non-pruned graph here we turn on aggressive coalescing</span><span>
</span><span id="line-84"></span><span>        </span><span class="hs-comment">--      to force all the (conservative) coalescences found during scanning.</span><span>
</span><span id="line-85"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-86"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680943801"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943801"><span class="hs-identifier hs-var">graph_scan_coalesced</span></a></span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[Maybe (k, k)]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span>
</span><span id="line-87"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Graph k cls color -&gt; (k, k) -&gt; (Graph k cls color, Maybe (k, k)))
-&gt; Graph k cls color
-&gt; [(k, k)]
-&gt; (Graph k cls color, [Maybe (k, k)])
forall (t :: * -&gt; *) s a b.
Traversable t =&gt;
(s -&gt; a -&gt; (s, b)) -&gt; s -&gt; t a -&gt; (s, t b)
</span><a href="../../base/src/Data.Traversable.html#mapAccumL"><span class="hs-identifier hs-var">mapAccumL</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (k, k)
-&gt; (Graph k cls color, Maybe (k, k))
forall k cls color.
(Uniquable k, Ord k, Eq cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (k, k)
-&gt; (Graph k cls color, Maybe (k, k))
</span><a href="GHC.Data.Graph.Ops.html#coalesceNodes"><span class="hs-identifier hs-var">coalesceNodes</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">True</span></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943820"><span class="hs-identifier hs-var">graph_coalesced</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943808"><span class="hs-identifier hs-var">kksCoalesce2</span></a></span><span>
</span><span id="line-88"></span><span>
</span><span id="line-89"></span><span>        </span><span class="hs-comment">-- color the trivially colorable nodes</span><span>
</span><span id="line-90"></span><span>        </span><span class="hs-comment">--      during scanning, keys of triv nodes were added to the front of the list as they were found</span><span>
</span><span id="line-91"></span><span>        </span><span class="hs-comment">--      this colors them in the reverse order, as required by the algorithm.</span><span>
</span><span id="line-92"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680943794"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943794"><span class="hs-identifier hs-var">graph_triv</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943793"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943793"><span class="hs-identifier hs-var">ksNoTriv</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-93"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; (Graph k cls color, [k])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="GHC.Data.Graph.Color.html#assignColors"><span class="hs-identifier hs-var">assignColors</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943836"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943801"><span class="hs-identifier hs-var">graph_scan_coalesced</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943810"><span class="hs-identifier hs-var">ksTriv</span></a></span><span>
</span><span id="line-94"></span><span>
</span><span id="line-95"></span><span>        </span><span class="hs-comment">-- try and color the problem nodes</span><span>
</span><span id="line-96"></span><span>        </span><span class="hs-comment">--      problem nodes are the ones that were left uncolored because they weren't triv.</span><span>
</span><span id="line-97"></span><span>        </span><span class="hs-comment">--      theres a change we can color them here anyway.</span><span>
</span><span id="line-98"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680943787"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943787"><span class="hs-identifier hs-var">graph_prob</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943786"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943786"><span class="hs-identifier hs-var">ksNoColor</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-99"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; (Graph k cls color, [k])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="GHC.Data.Graph.Color.html#assignColors"><span class="hs-identifier hs-var">assignColors</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943836"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943794"><span class="hs-identifier hs-var">graph_triv</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943809"><span class="hs-identifier hs-var">ksProblems</span></a></span><span>
</span><span id="line-100"></span><span>
</span><span id="line-101"></span><span>        </span><span class="hs-comment">-- if the trivially colorable nodes didn't color then something is probably wrong</span><span>
</span><span id="line-102"></span><span>        </span><span class="hs-comment">--      with the provided triv function.</span><span>
</span><span id="line-103"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-104"></span><span>   </span><span class="hs-keyword">in</span><span>   </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; Bool -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">[k] -&gt; Bool
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var">null</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943793"><span class="hs-identifier hs-var">ksNoTriv</span></a></span><span>
</span><span id="line-105"></span><span>         </span><span class="hs-keyword">then</span><span>   </span><span class="annot"><span class="annottext">String -&gt; SDoc -&gt; (Graph k cls color, UniqSet k, UniqFM k k)
forall a. HasCallStack =&gt; String -&gt; SDoc -&gt; a
</span><a href="GHC.Utils.Outputable.html#pprPanic"><span class="hs-identifier hs-var">pprPanic</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;colorGraph: trivially colorable nodes didn't color!&quot;</span></span><span> </span><span class="hs-comment">-- empty</span><span>
</span><span id="line-106"></span><span>                        </span><span class="hs-special">(</span><span>  </span><span class="annot"><span class="annottext">SDoc
</span><a href="GHC.Utils.Outputable.html#empty"><span class="hs-identifier hs-var">empty</span></a></span><span>
</span><span id="line-107"></span><span>                        </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%24%24"><span class="hs-operator hs-var">$$</span></a></span><span> </span><span class="annot"><span class="annottext">String -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;ksTriv    = &quot;</span></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%3E"><span class="hs-operator hs-var">&lt;&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">[k] -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943810"><span class="hs-identifier hs-var">ksTriv</span></a></span><span>
</span><span id="line-108"></span><span>                        </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%24%24"><span class="hs-operator hs-var">$$</span></a></span><span> </span><span class="annot"><span class="annottext">String -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;ksNoTriv  = &quot;</span></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%3E"><span class="hs-operator hs-var">&lt;&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">[k] -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943793"><span class="hs-identifier hs-var">ksNoTriv</span></a></span><span>
</span><span id="line-109"></span><span>                        </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%24%24"><span class="hs-operator hs-var">$$</span></a></span><span> </span><span class="annot"><span class="annottext">String -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;colors    = &quot;</span></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%3E"><span class="hs-operator hs-var">&lt;&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color) -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943836"><span class="hs-identifier hs-var">colors</span></a></span><span>
</span><span id="line-110"></span><span>                        </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%24%24"><span class="hs-operator hs-var">$$</span></a></span><span> </span><span class="annot"><span class="annottext">SDoc
</span><a href="GHC.Utils.Outputable.html#empty"><span class="hs-identifier hs-var">empty</span></a></span><span>
</span><span id="line-111"></span><span>                        </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%24%24"><span class="hs-operator hs-var">$$</span></a></span><span> </span><span class="annot"><span class="annottext">(color -&gt; SDoc) -&gt; Triv k cls color -&gt; Graph k cls color -&gt; SDoc
forall k cls color.
(Uniquable k, Outputable k, Outputable cls, Outputable color) =&gt;
(color -&gt; SDoc) -&gt; Triv k cls color -&gt; Graph k cls color -&gt; SDoc
</span><a href="GHC.Data.Graph.Ppr.html#dotGraph"><span class="hs-identifier hs-var">dotGraph</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="annot"><span class="annottext">color
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">String -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;white&quot;</span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943835"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943794"><span class="hs-identifier hs-var">graph_triv</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-112"></span><span>
</span><span id="line-113"></span><span>         </span><span class="hs-keyword">else</span><span>   </span><span class="hs-special">(</span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943787"><span class="hs-identifier hs-var">graph_prob</span></a></span><span>
</span><span id="line-114"></span><span>                </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[k] -&gt; UniqSet k
forall a. Uniquable a =&gt; [a] -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#mkUniqSet"><span class="hs-identifier hs-var">mkUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943786"><span class="hs-identifier hs-var">ksNoColor</span></a></span><span>   </span><span class="hs-comment">-- the nodes that didn't color (spills)</span><span>
</span><span id="line-115"></span><span>                </span><span class="hs-special">,</span><span> </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943838"><span class="hs-identifier hs-var">iterative</span></a></span><span>
</span><span id="line-116"></span><span>                        </span><span class="hs-keyword">then</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[(k, k)] -&gt; UniqFM k k
forall key elt. Uniquable key =&gt; [(key, elt)] -&gt; UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#listToUFM"><span class="hs-identifier hs-var">listToUFM</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943808"><span class="hs-identifier hs-var">kksCoalesce2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-117"></span><span>                        </span><span class="hs-keyword">else</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[(k, k)] -&gt; UniqFM k k
forall key elt. Uniquable key =&gt; [(key, elt)] -&gt; UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#listToUFM"><span class="hs-identifier hs-var">listToUFM</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943819"><span class="hs-identifier hs-var">kksCoalesce1</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-118"></span><span>
</span><span id="line-119"></span><span>
</span><span id="line-120"></span><span class="hs-comment">-- | Scan through the conflict graph separating out trivially colorable and</span><span>
</span><span id="line-121"></span><span class="hs-comment">--      potentially uncolorable (problem) nodes.</span><span>
</span><span id="line-122"></span><span class="hs-comment">--</span><span>
</span><span id="line-123"></span><span class="hs-comment">--      Checking whether a node is trivially colorable or not is a reasonably expensive operation,</span><span>
</span><span id="line-124"></span><span class="hs-comment">--      so after a triv node is found and removed from the graph it's no good to return to the 'start'</span><span>
</span><span id="line-125"></span><span class="hs-comment">--      of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.</span><span>
</span><span id="line-126"></span><span class="hs-comment">--</span><span>
</span><span id="line-127"></span><span class="hs-comment">--      To ward against this, during each pass through the graph we collect up a list of triv nodes</span><span>
</span><span id="line-128"></span><span class="hs-comment">--      that were found, and only remove them once we've finished the pass. The more nodes we can delete</span><span>
</span><span id="line-129"></span><span class="hs-comment">--      at once the more likely it is that nodes we've already checked will become trivially colorable</span><span>
</span><span id="line-130"></span><span class="hs-comment">--      for the next pass.</span><span>
</span><span id="line-131"></span><span class="hs-comment">--</span><span>
</span><span id="line-132"></span><span class="hs-comment">--      TODO:   add work lists to finding triv nodes is easier.</span><span>
</span><span id="line-133"></span><span class="hs-comment">--              If we've just scanned the graph, and removed triv nodes, then the only</span><span>
</span><span id="line-134"></span><span class="hs-comment">--              nodes that we need to rescan are the ones we've removed edges from.</span><span>
</span><span id="line-135"></span><span>
</span><span id="line-136"></span><span id="local-6989586621680943973"><span id="local-6989586621680943974"><span id="local-6989586621680943975"><span class="annot"><a href="GHC.Data.Graph.Color.html#colorScan"><span class="hs-identifier hs-type">colorScan</span></a></span><span>
</span><span id="line-137"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943973"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-138"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span>       </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span>
</span><span id="line-139"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-140"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span>                         </span><span class="hs-comment">-- ^ whether to do iterative coalescing</span><span>
</span><span id="line-141"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Triv"><span class="hs-identifier hs-type">Triv</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943973"><span class="hs-identifier hs-type">color</span></a></span><span>             </span><span class="hs-comment">-- ^ fn to decide whether a node is trivially colorable</span><span>
</span><span id="line-142"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943973"><span class="hs-identifier hs-type">color</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span>     </span><span class="hs-comment">-- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.</span><span>
</span><span id="line-143"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943974"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943973"><span class="hs-identifier hs-type">color</span></a></span><span>            </span><span class="hs-comment">-- ^ the graph to scan</span><span>
</span><span id="line-144"></span><span>
</span><span id="line-145"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680943975"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span class="hs-special">)</span></span></span></span><span>         </span><span class="hs-comment">--  triv colorable nodes, problem nodes, pairs of nodes to coalesce</span><span>
</span><span id="line-146"></span><span>
</span><span id="line-147"></span><span id="colorScan"><span class="annot"><span class="annottext">colorScan :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan"><span class="hs-identifier hs-var hs-var">colorScan</span></a></span></span><span> </span><span id="local-6989586621680943760"><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943760"><span class="hs-identifier hs-var">iterative</span></a></span></span><span> </span><span id="local-6989586621680943759"><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943759"><span class="hs-identifier hs-var">triv</span></a></span></span><span> </span><span id="local-6989586621680943758"><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943758"><span class="hs-identifier hs-var">spill</span></a></span></span><span> </span><span id="local-6989586621680943757"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943757"><span class="hs-identifier hs-var">graph</span></a></span></span><span>
</span><span id="line-148"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var">colorScan_spin</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943760"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943759"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943758"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943757"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-149"></span><span>
</span><span id="line-150"></span><span id="local-6989586621680943943"><span id="local-6989586621680943944"><span id="local-6989586621680943945"><span class="annot"><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-type">colorScan_spin</span></a></span><span>
</span><span id="line-151"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943943"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-152"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span>       </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span>
</span><span id="line-153"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-154"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span>
</span><span id="line-155"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Triv"><span class="hs-identifier hs-type">Triv</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943943"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-156"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943943"><span class="hs-identifier hs-type">color</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-157"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943944"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943943"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-158"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-159"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-160"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span>
</span><span id="line-161"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680943945"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-162"></span><span>
</span><span id="line-163"></span><span id="colorScan_spin"><span class="annot"><span class="annottext">colorScan_spin :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var hs-var">colorScan_spin</span></a></span></span><span> </span><span id="local-6989586621680943707"><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span></span><span> </span><span id="local-6989586621680943706"><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span></span><span> </span><span id="local-6989586621680943705"><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span></span><span> </span><span id="local-6989586621680943704"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span></span><span>
</span><span id="line-164"></span><span>        </span><span id="local-6989586621680943703"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span></span><span> </span><span id="local-6989586621680943702"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span></span><span> </span><span id="local-6989586621680943701"><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span></span><span>
</span><span id="line-165"></span><span>
</span><span id="line-166"></span><span>        </span><span class="hs-comment">-- if the graph is empty then we're done</span><span>
</span><span id="line-167"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">UniqFM k (Node k cls color) -&gt; Bool
forall key elt. UniqFM key elt -&gt; Bool
</span><a href="GHC.Types.Unique.FM.html#isNullUFM"><span class="hs-identifier hs-var">isNullUFM</span></a></span><span> </span><span class="annot"><span class="annottext">(UniqFM k (Node k cls color) -&gt; Bool)
-&gt; UniqFM k (Node k cls color) -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; UniqFM k (Node k cls color)
forall k cls color.
Graph k cls color -&gt; UniqFM k (Node k cls color)
</span><a href="GHC.Data.Graph.Base.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-168"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[(k, k)] -&gt; [(k, k)]
forall a. [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#reverse"><span class="hs-identifier hs-var">reverse</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-169"></span><span>
</span><span id="line-170"></span><span>        </span><span class="hs-comment">-- Simplify:</span><span>
</span><span id="line-171"></span><span>        </span><span class="hs-comment">--      Look for trivially colorable nodes.</span><span>
</span><span id="line-172"></span><span>        </span><span class="hs-comment">--      If we can find some then remove them from the graph and go back for more.</span><span>
</span><span id="line-173"></span><span>        </span><span class="hs-comment">--</span><span>
</span><span id="line-174"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span id="local-6989586621680943697"><span class="annot"><span class="annottext">nsTrivFound :: [Node k cls color]
</span><a href="#local-6989586621680943697"><span class="hs-identifier hs-var">nsTrivFound</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color
</span><span class="hs-identifier">_</span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span class="annot"><span class="annottext">[Node k cls color]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span>
</span><span id="line-175"></span><span>                </span><span class="hs-glyph">&lt;-</span><span>  </span><span class="annot"><span class="annottext">(Node k cls color -&gt; Bool)
-&gt; Graph k cls color -&gt; [Node k cls color]
forall k cls color.
(Node k cls color -&gt; Bool)
-&gt; Graph k cls color -&gt; [Node k cls color]
</span><a href="GHC.Data.Graph.Ops.html#scanGraph"><span class="hs-identifier hs-var">scanGraph</span></a></span><span>   </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621680943695"><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943695"><span class="hs-identifier hs-var">node</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span>  </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; cls
forall k cls color. Node k cls color -&gt; cls
</span><a href="GHC.Data.Graph.Base.html#nodeClass"><span class="hs-identifier hs-var hs-var">nodeClass</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943695"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; UniqSet k
forall k cls color. Node k cls color -&gt; UniqSet k
</span><a href="GHC.Data.Graph.Base.html#nodeConflicts"><span class="hs-identifier hs-var hs-var">nodeConflicts</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943695"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; UniqSet color
forall k cls color. Node k cls color -&gt; UniqSet color
</span><a href="GHC.Data.Graph.Base.html#nodeExclusions"><span class="hs-identifier hs-var hs-var">nodeExclusions</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943695"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-176"></span><span>
</span><span id="line-177"></span><span>                                  </span><span class="hs-comment">-- for iterative coalescing we only want non-move related</span><span>
</span><span id="line-178"></span><span>                                  </span><span class="hs-comment">--    nodes here</span><span>
</span><span id="line-179"></span><span>                                  </span><span class="annot"><span class="annottext">Bool -&gt; Bool -&gt; Bool
</span><span class="hs-operator hs-var">&amp;&amp;</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool -&gt; Bool
</span><span class="hs-operator hs-var">||</span></span><span> </span><span class="annot"><span class="annottext">UniqSet k -&gt; Bool
forall a. UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#isEmptyUniqSet"><span class="hs-identifier hs-var">isEmptyUniqSet</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; UniqSet k
forall k cls color. Node k cls color -&gt; UniqSet k
</span><a href="GHC.Data.Graph.Base.html#nodeCoalesce"><span class="hs-identifier hs-var hs-var">nodeCoalesce</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943695"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-180"></span><span>                        </span><span class="annot"><span class="annottext">(Graph k cls color -&gt; [Node k cls color])
-&gt; Graph k cls color -&gt; [Node k cls color]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-181"></span><span>
</span><span id="line-182"></span><span>        </span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943687"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943687"><span class="hs-identifier hs-var">ksTrivFound</span></a></span></span><span>   </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(Node k cls color -&gt; k) -&gt; [Node k cls color] -&gt; [k]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color -&gt; k
forall k cls color. Node k cls color -&gt; k
</span><a href="GHC.Data.Graph.Base.html#nodeId"><span class="hs-identifier hs-var hs-var">nodeId</span></a></span><span> </span><span class="annot"><span class="annottext">[Node k cls color]
</span><a href="#local-6989586621680943697"><span class="hs-identifier hs-var">nsTrivFound</span></a></span><span>
</span><span id="line-183"></span><span>        </span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943685"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943685"><span class="hs-identifier hs-var">graph2</span></a></span></span><span>        </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(k -&gt; Graph k cls color -&gt; Graph k cls color)
-&gt; Graph k cls color -&gt; [k] -&gt; Graph k cls color
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var">foldr</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621680943683"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943683"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621680943682"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943682"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">let</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943680"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943680"><span class="hs-identifier hs-var">g'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
forall k cls color.
Uniquable k =&gt;
k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
</span><a href="GHC.Data.Graph.Ops.html#delNode"><span class="hs-identifier hs-var">delNode</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943683"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943682"><span class="hs-identifier hs-var">g</span></a></span><span>
</span><span id="line-184"></span><span>                                          </span><span class="hs-keyword">in</span><span>  </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943680"><span class="hs-identifier hs-var">g'</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-185"></span><span>                                </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943687"><span class="hs-identifier hs-var">ksTrivFound</span></a></span><span>
</span><span id="line-186"></span><span>
</span><span id="line-187"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var">colorScan_spin</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943685"><span class="hs-identifier hs-var">graph2</span></a></span><span>
</span><span id="line-188"></span><span>                </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943687"><span class="hs-identifier hs-var">ksTrivFound</span></a></span><span> </span><span class="annot"><span class="annottext">[k] -&gt; [k] -&gt; [k]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-189"></span><span>                </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span>
</span><span id="line-190"></span><span>                </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span>
</span><span id="line-191"></span><span>
</span><span id="line-192"></span><span>        </span><span class="hs-comment">-- Coalesce:</span><span>
</span><span id="line-193"></span><span>        </span><span class="hs-comment">--      If we're doing iterative coalescing and no triv nodes are available</span><span>
</span><span id="line-194"></span><span>        </span><span class="hs-comment">--      then it's time for a coalescing pass.</span><span>
</span><span id="line-195"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span>
</span><span id="line-196"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
forall k cls color.
(Uniquable k, Ord k, Eq cls, Outputable k) =&gt;
Bool
-&gt; Triv k cls color
-&gt; Graph k cls color
-&gt; (Graph k cls color, [(k, k)])
</span><a href="GHC.Data.Graph.Ops.html#coalesceGraph"><span class="hs-identifier hs-var">coalesceGraph</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-197"></span><span>
</span><span id="line-198"></span><span>                </span><span class="hs-comment">-- we were able to coalesce something</span><span>
</span><span id="line-199"></span><span>                </span><span class="hs-comment">--      go back to Simplify and see if this frees up more nodes to be trivially colorable.</span><span>
</span><span id="line-200"></span><span>                </span><span class="hs-special">(</span><span id="local-6989586621680943678"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943678"><span class="hs-identifier hs-var">graph2</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943677"><span class="annot"><span class="annottext">kksCoalesceFound :: [(k, k)]
</span><a href="#local-6989586621680943677"><span class="hs-identifier hs-var">kksCoalesceFound</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><span class="annottext">(k, k)
</span><span class="hs-identifier">_</span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span class="annot"><span class="annottext">[(k, k)]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-201"></span><span>                 </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var">colorScan_spin</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943678"><span class="hs-identifier hs-var">graph2</span></a></span><span>
</span><span id="line-202"></span><span>                        </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[(k, k)] -&gt; [(k, k)]
forall a. [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#reverse"><span class="hs-identifier hs-var">reverse</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943677"><span class="hs-identifier hs-var">kksCoalesceFound</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)] -&gt; [(k, k)] -&gt; [(k, k)]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-203"></span><span>
</span><span id="line-204"></span><span>                </span><span class="hs-comment">-- Freeze:</span><span>
</span><span id="line-205"></span><span>                </span><span class="hs-comment">-- nothing could be coalesced (or was triv),</span><span>
</span><span id="line-206"></span><span>                </span><span class="hs-comment">--      time to choose a node to freeze and give up on ever coalescing it.</span><span>
</span><span id="line-207"></span><span>                </span><span class="hs-special">(</span><span id="local-6989586621680943676"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943676"><span class="hs-identifier hs-var">graph2</span></a></span></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-208"></span><span>                 </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; (Graph k cls color, Bool)
forall k cls color.
Uniquable k =&gt;
Graph k cls color -&gt; (Graph k cls color, Bool)
</span><a href="GHC.Data.Graph.Ops.html#freezeOneInGraph"><span class="hs-identifier hs-var">freezeOneInGraph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943676"><span class="hs-identifier hs-var">graph2</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-209"></span><span>
</span><span id="line-210"></span><span>                        </span><span class="hs-comment">-- we were able to freeze something</span><span>
</span><span id="line-211"></span><span>                        </span><span class="hs-comment">--      hopefully this will free up something for Simplify</span><span>
</span><span id="line-212"></span><span>                        </span><span class="hs-special">(</span><span id="local-6989586621680943674"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943674"><span class="hs-identifier hs-var">graph3</span></a></span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">True</span></span><span class="hs-special">)</span><span>
</span><span id="line-213"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var">colorScan_spin</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943674"><span class="hs-identifier hs-var">graph3</span></a></span><span>
</span><span id="line-214"></span><span>                                </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span>
</span><span id="line-215"></span><span>
</span><span id="line-216"></span><span>                        </span><span class="hs-comment">-- we couldn't find something to freeze either</span><span>
</span><span id="line-217"></span><span>                        </span><span class="hs-comment">--      time for a spill</span><span>
</span><span id="line-218"></span><span>                        </span><span class="hs-special">(</span><span id="local-6989586621680943673"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943673"><span class="hs-identifier hs-var">graph3</span></a></span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span class="hs-special">)</span><span>
</span><span id="line-219"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spill"><span class="hs-identifier hs-var">colorScan_spill</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943673"><span class="hs-identifier hs-var">graph3</span></a></span><span>
</span><span id="line-220"></span><span>                                </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span>
</span><span id="line-221"></span><span>
</span><span id="line-222"></span><span>        </span><span class="hs-comment">-- spill time</span><span>
</span><span id="line-223"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>
</span><span id="line-224"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spill"><span class="hs-identifier hs-var">colorScan_spill</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943707"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943706"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943705"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943704"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-225"></span><span>                </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943703"><span class="hs-identifier hs-var">ksTriv</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943702"><span class="hs-identifier hs-var">ksSpill</span></a></span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943701"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span>
</span><span id="line-226"></span><span>
</span><span id="line-227"></span><span>
</span><span id="line-228"></span><span class="hs-comment">-- Select:</span><span>
</span><span id="line-229"></span><span class="hs-comment">-- we couldn't find any triv nodes or things to freeze or coalesce,</span><span>
</span><span id="line-230"></span><span class="hs-comment">--      and the graph isn't empty yet.. We'll have to choose a spill</span><span>
</span><span id="line-231"></span><span class="hs-comment">--      candidate and leave it uncolored.</span><span>
</span><span id="line-232"></span><span class="hs-comment">--</span><span>
</span><span id="line-233"></span><span id="local-6989586621680943669"><span id="local-6989586621680943670"><span id="local-6989586621680943671"><span class="annot"><a href="GHC.Data.Graph.Color.html#colorScan_spill"><span class="hs-identifier hs-type">colorScan_spill</span></a></span><span>
</span><span id="line-234"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943669"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-235"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span>       </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span>
</span><span id="line-236"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-237"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span>
</span><span id="line-238"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Triv"><span class="hs-identifier hs-type">Triv</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943669"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-239"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943669"><span class="hs-identifier hs-type">color</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-240"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943670"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943669"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-241"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-242"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-243"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span>
</span><span id="line-244"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680943671"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-245"></span><span>
</span><span id="line-246"></span><span id="colorScan_spill"><span class="annot"><span class="annottext">colorScan_spill :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spill"><span class="hs-identifier hs-var hs-var">colorScan_spill</span></a></span></span><span> </span><span id="local-6989586621680943654"><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943654"><span class="hs-identifier hs-var">iterative</span></a></span></span><span> </span><span id="local-6989586621680943653"><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943653"><span class="hs-identifier hs-var">triv</span></a></span></span><span> </span><span id="local-6989586621680943652"><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943652"><span class="hs-identifier hs-var">spill</span></a></span></span><span> </span><span id="local-6989586621680943651"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943651"><span class="hs-identifier hs-var">graph</span></a></span></span><span>
</span><span id="line-247"></span><span>        </span><span id="local-6989586621680943650"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943650"><span class="hs-identifier hs-var">ksTriv</span></a></span></span><span> </span><span id="local-6989586621680943649"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943649"><span class="hs-identifier hs-var">ksSpill</span></a></span></span><span> </span><span id="local-6989586621680943648"><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943648"><span class="hs-identifier hs-var">kksCoalesce</span></a></span></span><span>
</span><span id="line-248"></span><span>
</span><span id="line-249"></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">let</span><span>  </span><span id="local-6989586621680943647"><span class="annot"><span class="annottext">kSpill :: k
</span><a href="#local-6989586621680943647"><span class="hs-identifier hs-var hs-var">kSpill</span></a></span></span><span>          </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943652"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943651"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-250"></span><span>        </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943645"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943645"><span class="hs-identifier hs-var">graph'</span></a></span></span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
forall k cls color.
Uniquable k =&gt;
k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
</span><a href="GHC.Data.Graph.Ops.html#delNode"><span class="hs-identifier hs-var">delNode</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943647"><span class="hs-identifier hs-var">kSpill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943651"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-251"></span><span>   </span><span class="hs-keyword">in</span><span>   </span><span class="annot"><span class="annottext">Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Ord k, Eq cls,
 Outputable k, Outputable cls) =&gt;
Bool
-&gt; Triv k cls color
-&gt; (Graph k cls color -&gt; k)
-&gt; Graph k cls color
-&gt; [k]
-&gt; [k]
-&gt; [(k, k)]
-&gt; ([k], [k], [(k, k)])
</span><a href="GHC.Data.Graph.Color.html#colorScan_spin"><span class="hs-identifier hs-var">colorScan_spin</span></a></span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="#local-6989586621680943654"><span class="hs-identifier hs-var">iterative</span></a></span><span> </span><span class="annot"><span class="annottext">Triv k cls color
</span><a href="#local-6989586621680943653"><span class="hs-identifier hs-var">triv</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k
</span><a href="#local-6989586621680943652"><span class="hs-identifier hs-var">spill</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943645"><span class="hs-identifier hs-var">graph'</span></a></span><span>
</span><span id="line-252"></span><span>                </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943650"><span class="hs-identifier hs-var">ksTriv</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943647"><span class="hs-identifier hs-var">kSpill</span></a></span><span> </span><span class="annot"><span class="annottext">k -&gt; [k] -&gt; [k]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943649"><span class="hs-identifier hs-var">ksSpill</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[(k, k)]
</span><a href="#local-6989586621680943648"><span class="hs-identifier hs-var">kksCoalesce</span></a></span><span>
</span><span id="line-253"></span><span>
</span><span id="line-254"></span><span>
</span><span id="line-255"></span><span class="hs-comment">-- | Try to assign a color to all these nodes.</span><span>
</span><span id="line-256"></span><span>
</span><span id="line-257"></span><span class="annot"><a href="GHC.Data.Graph.Color.html#assignColors"><span class="hs-identifier hs-type">assignColors</span></a></span><span>
</span><span id="line-258"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-keyword">forall</span><span> </span><span id="local-6989586621680943965"><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span></span><span> </span><span id="local-6989586621680943964"><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span></span><span> </span><span id="local-6989586621680943963"><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span></span><span class="hs-operator">.</span><span>
</span><span id="line-259"></span><span>           </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-260"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-261"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Types.Unique.Set.html#UniqSet"><span class="hs-identifier hs-type">UniqSet</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span class="hs-special">)</span><span>       </span><span class="hs-comment">-- ^ map of (node class -&gt; set of colors available for this class).</span><span>
</span><span id="line-262"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span>            </span><span class="hs-comment">-- ^ the graph</span><span>
</span><span id="line-263"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>                          </span><span class="hs-comment">-- ^ nodes to assign a color to.</span><span>
</span><span id="line-264"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span>          </span><span class="hs-comment">-- the colored graph</span><span>
</span><span id="line-265"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span>                       </span><span class="hs-comment">-- the nodes that didn't color.</span><span>
</span><span id="line-266"></span><span>
</span><span id="line-267"></span><span id="assignColors"><span class="annot"><span class="annottext">assignColors :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="GHC.Data.Graph.Color.html#assignColors"><span class="hs-identifier hs-var hs-var">assignColors</span></a></span></span><span> </span><span id="local-6989586621680943636"><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943636"><span class="hs-identifier hs-var">colors</span></a></span></span><span> </span><span id="local-6989586621680943635"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943635"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680943634"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943634"><span class="hs-identifier hs-var">ks</span></a></span></span><span>
</span><span id="line-268"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="#local-6989586621680943633"><span class="hs-identifier hs-var">assignColors'</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943636"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943635"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943634"><span class="hs-identifier hs-var">ks</span></a></span><span>
</span><span id="line-269"></span><span>
</span><span id="line-270"></span><span> </span><span class="hs-keyword">where</span><span>  </span><span class="annot"><a href="#local-6989586621680943633"><span class="hs-identifier hs-type">assignColors'</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Types.Unique.Set.html#UniqSet"><span class="hs-identifier hs-type">UniqSet</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span class="hs-special">)</span><span>       </span><span class="hs-comment">-- ^ map of (node class -&gt; set of colors available for this class).</span><span>
</span><span id="line-271"></span><span>                        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span>            </span><span class="hs-comment">-- ^ the graph</span><span>
</span><span id="line-272"></span><span>                        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>                          </span><span class="hs-comment">-- ^ nodes to assign a color to.</span><span>
</span><span id="line-273"></span><span>                        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-274"></span><span>                        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943964"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943963"><span class="hs-identifier hs-type">color</span></a></span><span>          </span><span class="hs-comment">-- the colored graph</span><span>
</span><span id="line-275"></span><span>                        </span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680943965"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-276"></span><span>        </span><span id="local-6989586621680943633"><span class="annot"><span class="annottext">assignColors' :: UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="#local-6989586621680943633"><span class="hs-identifier hs-var hs-var">assignColors'</span></a></span></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621680943632"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943632"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680943631"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943631"><span class="hs-identifier hs-var">prob</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-277"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943632"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943631"><span class="hs-identifier hs-var">prob</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-278"></span><span>
</span><span id="line-279"></span><span>        </span><span class="annot"><a href="#local-6989586621680943633"><span class="hs-identifier hs-var">assignColors'</span></a></span><span> </span><span id="local-6989586621680943630"><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943630"><span class="hs-identifier hs-var">colors</span></a></span></span><span> </span><span id="local-6989586621680943629"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943629"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680943628"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943628"><span class="hs-identifier hs-var">prob</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680943627"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943627"><span class="hs-identifier hs-var">k</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621680943626"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943626"><span class="hs-identifier hs-var">ks</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-280"></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
forall {k} {cls} {color}.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color)
-&gt; k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
</span><a href="#local-6989586621680943625"><span class="hs-identifier hs-var">assignColor</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943630"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943627"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943629"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-281"></span><span>
</span><span id="line-282"></span><span>                </span><span class="hs-comment">-- couldn't color this node</span><span>
</span><span id="line-283"></span><span>                </span><span class="annot"><span class="annottext">Maybe (Graph k cls color)
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="#local-6989586621680943633"><span class="hs-identifier hs-var">assignColors'</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943630"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943629"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943627"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">k -&gt; [k] -&gt; [k]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943628"><span class="hs-identifier hs-var">prob</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943626"><span class="hs-identifier hs-var">ks</span></a></span><span>
</span><span id="line-284"></span><span>
</span><span id="line-285"></span><span>                </span><span class="hs-comment">-- this node colored ok, so do the rest</span><span>
</span><span id="line-286"></span><span>                </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943624"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943624"><span class="hs-identifier hs-var">graph'</span></a></span></span><span>     </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
-&gt; Graph k cls color -&gt; [k] -&gt; [k] -&gt; (Graph k cls color, [k])
</span><a href="#local-6989586621680943633"><span class="hs-identifier hs-var">assignColors'</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943630"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943624"><span class="hs-identifier hs-var">graph'</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943628"><span class="hs-identifier hs-var">prob</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621680943626"><span class="hs-identifier hs-var">ks</span></a></span><span>
</span><span id="line-287"></span><span>
</span><span id="line-288"></span><span>
</span><span id="line-289"></span><span>        </span><span id="local-6989586621680943625"><span class="annot"><span class="annottext">assignColor :: UniqFM cls (UniqSet color)
-&gt; k -&gt; Graph k cls color -&gt; Maybe (Graph k cls color)
</span><a href="#local-6989586621680943625"><span class="hs-identifier hs-var hs-var">assignColor</span></a></span></span><span> </span><span id="local-6989586621680943614"><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943614"><span class="hs-identifier hs-var">colors</span></a></span></span><span> </span><span id="local-6989586621680943613"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943613"><span class="hs-identifier hs-var">u</span></a></span></span><span> </span><span id="local-6989586621680943612"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943612"><span class="hs-identifier hs-var">graph</span></a></span></span><span>
</span><span id="line-290"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943611"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943611"><span class="hs-identifier hs-var">c</span></a></span></span><span>        </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color) -&gt; Graph k cls color -&gt; k -&gt; Maybe color
forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color) -&gt; Graph k cls color -&gt; k -&gt; Maybe color
</span><a href="GHC.Data.Graph.Color.html#selectColor"><span class="hs-identifier hs-var">selectColor</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943614"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943612"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943613"><span class="hs-identifier hs-var">u</span></a></span><span>
</span><span id="line-291"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; Maybe (Graph k cls color)
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">k -&gt; color -&gt; Graph k cls color -&gt; Graph k cls color
forall k color cls.
Uniquable k =&gt;
k -&gt; color -&gt; Graph k cls color -&gt; Graph k cls color
</span><a href="GHC.Data.Graph.Ops.html#setColor"><span class="hs-identifier hs-var">setColor</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943613"><span class="hs-identifier hs-var">u</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943611"><span class="hs-identifier hs-var">c</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943612"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-292"></span><span>
</span><span id="line-293"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>
</span><span id="line-294"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe (Graph k cls color)
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>
</span><span id="line-295"></span><span>
</span><span id="line-296"></span><span>
</span><span id="line-297"></span><span>
</span><span id="line-298"></span><span class="hs-comment">-- | Select a color for a certain node</span><span>
</span><span id="line-299"></span><span class="hs-comment">--      taking into account preferences, neighbors and exclusions.</span><span>
</span><span id="line-300"></span><span class="hs-comment">--      returns Nothing if no color can be assigned to this node.</span><span>
</span><span id="line-301"></span><span class="hs-comment">--</span><span>
</span><span id="line-302"></span><span id="local-6989586621680943894"><span id="local-6989586621680943895"><span id="local-6989586621680943896"><span class="annot"><a href="GHC.Data.Graph.Color.html#selectColor"><span class="hs-identifier hs-type">selectColor</span></a></span><span>
</span><span id="line-303"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943896"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943895"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943894"><span class="hs-identifier hs-type">color</span></a></span><span>
</span><span id="line-304"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943895"><span class="hs-identifier hs-type">cls</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-305"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943895"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Types.Unique.Set.html#UniqSet"><span class="hs-identifier hs-type">UniqSet</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943894"><span class="hs-identifier hs-type">color</span></a></span><span class="hs-special">)</span><span>       </span><span class="hs-comment">-- ^ map of (node class -&gt; set of colors available for this class).</span><span>
</span><span id="line-306"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Base.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943896"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943895"><span class="hs-identifier hs-type">cls</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943894"><span class="hs-identifier hs-type">color</span></a></span><span>            </span><span class="hs-comment">-- ^ the graph</span><span>
</span><span id="line-307"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680943896"><span class="hs-identifier hs-type">k</span></a></span><span>                            </span><span class="hs-comment">-- ^ key of the node to select a color for.</span><span>
</span><span id="line-308"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680943894"><span class="hs-identifier hs-type">color</span></a></span></span></span></span><span>
</span><span id="line-309"></span><span>
</span><span id="line-310"></span><span id="selectColor"><span class="annot"><span class="annottext">selectColor :: forall k cls color.
(Uniquable k, Uniquable cls, Uniquable color, Outputable cls) =&gt;
UniqFM cls (UniqSet color) -&gt; Graph k cls color -&gt; k -&gt; Maybe color
</span><a href="GHC.Data.Graph.Color.html#selectColor"><span class="hs-identifier hs-var hs-var">selectColor</span></a></span></span><span> </span><span id="local-6989586621680943604"><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943604"><span class="hs-identifier hs-var">colors</span></a></span></span><span> </span><span id="local-6989586621680943603"><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943603"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680943602"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943602"><span class="hs-identifier hs-var">u</span></a></span></span><span>
</span><span id="line-311"></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">let</span><span>  </span><span class="hs-comment">-- lookup the node</span><span>
</span><span id="line-312"></span><span>        </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943600"><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span></span><span>       </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph k cls color -&gt; k -&gt; Maybe (Node k cls color)
forall k cls color.
Uniquable k =&gt;
Graph k cls color -&gt; k -&gt; Maybe (Node k cls color)
</span><a href="GHC.Data.Graph.Ops.html#lookupNode"><span class="hs-identifier hs-var">lookupNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943603"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621680943602"><span class="hs-identifier hs-var">u</span></a></span><span>
</span><span id="line-313"></span><span>
</span><span id="line-314"></span><span>        </span><span class="hs-comment">-- lookup the available colors for the class of this node.</span><span>
</span><span id="line-315"></span><span>        </span><span id="local-6989586621680943594"><span class="annot"><span class="annottext">colors_avail :: UniqSet color
</span><a href="#local-6989586621680943594"><span class="hs-identifier hs-var hs-var">colors_avail</span></a></span></span><span>
</span><span id="line-316"></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color) -&gt; cls -&gt; Maybe (UniqSet color)
forall key elt. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; Maybe elt
</span><a href="GHC.Types.Unique.FM.html#lookupUFM"><span class="hs-identifier hs-var">lookupUFM</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM cls (UniqSet color)
</span><a href="#local-6989586621680943604"><span class="hs-identifier hs-var">colors</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; cls
forall k cls color. Node k cls color -&gt; cls
</span><a href="GHC.Data.Graph.Base.html#nodeClass"><span class="hs-identifier hs-var hs-var">nodeClass</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-317"></span><span>                </span><span class="annot"><span class="annottext">Maybe (UniqSet color)
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">String -&gt; SDoc -&gt; UniqSet color
forall a. HasCallStack =&gt; String -&gt; SDoc -&gt; a
</span><a href="GHC.Utils.Outputable.html#pprPanic"><span class="hs-identifier hs-var">pprPanic</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;selectColor: no colors available for class &quot;</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">cls -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; cls
forall k cls color. Node k cls color -&gt; cls
</span><a href="GHC.Data.Graph.Base.html#nodeClass"><span class="hs-identifier hs-var hs-var">nodeClass</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-318"></span><span>                </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943592"><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943592"><span class="hs-identifier hs-var">cs</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943592"><span class="hs-identifier hs-var">cs</span></a></span><span>
</span><span id="line-319"></span><span>
</span><span id="line-320"></span><span>        </span><span class="hs-comment">-- find colors we can't use because they're already being used</span><span>
</span><span id="line-321"></span><span>        </span><span class="hs-comment">--      by a node that conflicts with this one.</span><span>
</span><span id="line-322"></span><span>        </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680943587"><span class="annot"><span class="annottext">[Node k cls color]
</span><a href="#local-6989586621680943587"><span class="hs-identifier hs-var">nsConflicts</span></a></span></span><span>
</span><span id="line-323"></span><span>                        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Maybe (Node k cls color)] -&gt; Maybe [Node k cls color]
forall (t :: * -&gt; *) (m :: * -&gt; *) a.
(Traversable t, Monad m) =&gt;
t (m a) -&gt; m (t a)
</span><a href="../../base/src/Data.Traversable.html#sequence"><span class="hs-identifier hs-var">sequence</span></a></span><span>
</span><span id="line-324"></span><span>                        </span><span class="annot"><span class="annottext">([Maybe (Node k cls color)] -&gt; Maybe [Node k cls color])
-&gt; [Maybe (Node k cls color)] -&gt; Maybe [Node k cls color]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">(k -&gt; Maybe (Node k cls color))
-&gt; [k] -&gt; [Maybe (Node k cls color)]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph k cls color -&gt; k -&gt; Maybe (Node k cls color)
forall k cls color.
Uniquable k =&gt;
Graph k cls color -&gt; k -&gt; Maybe (Node k cls color)
</span><a href="GHC.Data.Graph.Ops.html#lookupNode"><span class="hs-identifier hs-var">lookupNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph k cls color
</span><a href="#local-6989586621680943603"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-325"></span><span>                        </span><span class="annot"><span class="annottext">([k] -&gt; [Maybe (Node k cls color)])
-&gt; [k] -&gt; [Maybe (Node k cls color)]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet k -&gt; [k]
forall elt. UniqSet elt -&gt; [elt]
</span><a href="GHC.Types.Unique.Set.html#nonDetEltsUniqSet"><span class="hs-identifier hs-var">nonDetEltsUniqSet</span></a></span><span>
</span><span id="line-326"></span><span>                        </span><span class="annot"><span class="annottext">(UniqSet k -&gt; [k]) -&gt; UniqSet k -&gt; [k]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color -&gt; UniqSet k
forall k cls color. Node k cls color -&gt; UniqSet k
</span><a href="GHC.Data.Graph.Base.html#nodeConflicts"><span class="hs-identifier hs-var hs-var">nodeConflicts</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span>
</span><span id="line-327"></span><span>                        </span><span class="hs-comment">-- See Note [Unique Determinism and code generation]</span><span>
</span><span id="line-328"></span><span>
</span><span id="line-329"></span><span>        </span><span id="local-6989586621680943583"><span class="annot"><span class="annottext">colors_conflict :: UniqSet color
</span><a href="#local-6989586621680943583"><span class="hs-identifier hs-var hs-var">colors_conflict</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[color] -&gt; UniqSet color
forall a. Uniquable a =&gt; [a] -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#mkUniqSet"><span class="hs-identifier hs-var">mkUniqSet</span></a></span><span>
</span><span id="line-330"></span><span>                        </span><span class="annot"><span class="annottext">([color] -&gt; UniqSet color) -&gt; [color] -&gt; UniqSet color
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">[Maybe color] -&gt; [color]
forall a. [Maybe a] -&gt; [a]
</span><a href="../../base/src/Data.Maybe.html#catMaybes"><span class="hs-identifier hs-var">catMaybes</span></a></span><span>
</span><span id="line-331"></span><span>                        </span><span class="annot"><span class="annottext">([Maybe color] -&gt; [color]) -&gt; [Maybe color] -&gt; [color]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">(Node k cls color -&gt; Maybe color)
-&gt; [Node k cls color] -&gt; [Maybe color]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color -&gt; Maybe color
forall k cls color. Node k cls color -&gt; Maybe color
</span><a href="GHC.Data.Graph.Base.html#nodeColor"><span class="hs-identifier hs-var hs-var">nodeColor</span></a></span><span> </span><span class="annot"><span class="annottext">[Node k cls color]
</span><a href="#local-6989586621680943587"><span class="hs-identifier hs-var">nsConflicts</span></a></span><span>
</span><span id="line-332"></span><span>
</span><span id="line-333"></span><span>        </span><span class="hs-comment">-- the prefs of our neighbors</span><span>
</span><span id="line-334"></span><span>        </span><span id="local-6989586621680943578"><span class="annot"><span class="annottext">colors_neighbor_prefs :: UniqSet color
</span><a href="#local-6989586621680943578"><span class="hs-identifier hs-var hs-var">colors_neighbor_prefs</span></a></span></span><span>
</span><span id="line-335"></span><span>                        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[color] -&gt; UniqSet color
forall a. Uniquable a =&gt; [a] -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#mkUniqSet"><span class="hs-identifier hs-var">mkUniqSet</span></a></span><span>
</span><span id="line-336"></span><span>                        </span><span class="annot"><span class="annottext">([color] -&gt; UniqSet color) -&gt; [color] -&gt; UniqSet color
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">(Node k cls color -&gt; [color]) -&gt; [Node k cls color] -&gt; [color]
forall (t :: * -&gt; *) a b. Foldable t =&gt; (a -&gt; [b]) -&gt; t a -&gt; [b]
</span><a href="../../base/src/Data.Foldable.html#concatMap"><span class="hs-identifier hs-var">concatMap</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color -&gt; [color]
forall k cls color. Node k cls color -&gt; [color]
</span><a href="GHC.Data.Graph.Base.html#nodePreference"><span class="hs-identifier hs-var hs-var">nodePreference</span></a></span><span> </span><span class="annot"><span class="annottext">[Node k cls color]
</span><a href="#local-6989586621680943587"><span class="hs-identifier hs-var">nsConflicts</span></a></span><span>
</span><span id="line-337"></span><span>
</span><span id="line-338"></span><span>        </span><span class="hs-comment">-- colors that are still valid for us</span><span>
</span><span id="line-339"></span><span>        </span><span id="local-6989586621680943575"><span class="annot"><span class="annottext">colors_ok_ex :: UniqSet color
</span><a href="#local-6989586621680943575"><span class="hs-identifier hs-var hs-var">colors_ok_ex</span></a></span></span><span>    </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; UniqSet color -&gt; UniqSet color
forall a. UniqSet a -&gt; UniqSet a -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#minusUniqSet"><span class="hs-identifier hs-var">minusUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943594"><span class="hs-identifier hs-var">colors_avail</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; UniqSet color
forall k cls color. Node k cls color -&gt; UniqSet color
</span><a href="GHC.Data.Graph.Base.html#nodeExclusions"><span class="hs-identifier hs-var hs-var">nodeExclusions</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-340"></span><span>        </span><span id="local-6989586621680943573"><span class="annot"><span class="annottext">colors_ok :: UniqSet color
</span><a href="#local-6989586621680943573"><span class="hs-identifier hs-var hs-var">colors_ok</span></a></span></span><span>       </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; UniqSet color -&gt; UniqSet color
forall a. UniqSet a -&gt; UniqSet a -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#minusUniqSet"><span class="hs-identifier hs-var">minusUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943575"><span class="hs-identifier hs-var">colors_ok_ex</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943583"><span class="hs-identifier hs-var">colors_conflict</span></a></span><span>
</span><span id="line-341"></span><span>
</span><span id="line-342"></span><span>        </span><span class="hs-comment">-- the colors that we prefer, and are still ok</span><span>
</span><span id="line-343"></span><span>        </span><span id="local-6989586621680943571"><span class="annot"><span class="annottext">colors_ok_pref :: UniqSet color
</span><a href="#local-6989586621680943571"><span class="hs-identifier hs-var hs-var">colors_ok_pref</span></a></span></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; UniqSet color -&gt; UniqSet color
forall a. UniqSet a -&gt; UniqSet a -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#intersectUniqSets"><span class="hs-identifier hs-var">intersectUniqSets</span></a></span><span>
</span><span id="line-344"></span><span>                                </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[color] -&gt; UniqSet color
forall a. Uniquable a =&gt; [a] -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#mkUniqSet"><span class="hs-identifier hs-var">mkUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">([color] -&gt; UniqSet color) -&gt; [color] -&gt; UniqSet color
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color -&gt; [color]
forall k cls color. Node k cls color -&gt; [color]
</span><a href="GHC.Data.Graph.Base.html#nodePreference"><span class="hs-identifier hs-var hs-var">nodePreference</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943573"><span class="hs-identifier hs-var">colors_ok</span></a></span><span>
</span><span id="line-345"></span><span>
</span><span id="line-346"></span><span>        </span><span class="hs-comment">-- the colors that we could choose while being nice to our neighbors</span><span>
</span><span id="line-347"></span><span>        </span><span id="local-6989586621680943569"><span class="annot"><span class="annottext">colors_ok_nice :: UniqSet color
</span><a href="#local-6989586621680943569"><span class="hs-identifier hs-var hs-var">colors_ok_nice</span></a></span></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; UniqSet color -&gt; UniqSet color
forall a. UniqSet a -&gt; UniqSet a -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#minusUniqSet"><span class="hs-identifier hs-var">minusUniqSet</span></a></span><span>
</span><span id="line-348"></span><span>                                </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943573"><span class="hs-identifier hs-var">colors_ok</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943578"><span class="hs-identifier hs-var">colors_neighbor_prefs</span></a></span><span>
</span><span id="line-349"></span><span>
</span><span id="line-350"></span><span>        </span><span class="hs-comment">-- the best of all possible worlds..</span><span>
</span><span id="line-351"></span><span>        </span><span id="local-6989586621680943568"><span class="annot"><span class="annottext">colors_ok_pref_nice :: UniqSet color
</span><a href="#local-6989586621680943568"><span class="hs-identifier hs-var hs-var">colors_ok_pref_nice</span></a></span></span><span>
</span><span id="line-352"></span><span>                        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; UniqSet color -&gt; UniqSet color
forall a. UniqSet a -&gt; UniqSet a -&gt; UniqSet a
</span><a href="GHC.Types.Unique.Set.html#intersectUniqSets"><span class="hs-identifier hs-var">intersectUniqSets</span></a></span><span>
</span><span id="line-353"></span><span>                                </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943569"><span class="hs-identifier hs-var">colors_ok_nice</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943571"><span class="hs-identifier hs-var">colors_ok_pref</span></a></span><span>
</span><span id="line-354"></span><span>
</span><span id="line-355"></span><span>        </span><span class="hs-comment">-- make the decision</span><span>
</span><span id="line-356"></span><span>        </span><span id="local-6989586621680943565"><span class="annot"><span class="annottext">chooseColor :: Maybe color
</span><a href="#local-6989586621680943565"><span class="hs-identifier hs-var hs-var">chooseColor</span></a></span></span><span>
</span><span id="line-357"></span><span>
</span><span id="line-358"></span><span>                </span><span class="hs-comment">-- everyone is happy, yay!</span><span>
</span><span id="line-359"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; Bool -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; Bool
forall a. UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#isEmptyUniqSet"><span class="hs-identifier hs-var">isEmptyUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943568"><span class="hs-identifier hs-var">colors_ok_pref_nice</span></a></span><span>
</span><span id="line-360"></span><span>                </span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943564"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943564"><span class="hs-identifier hs-var">c</span></a></span></span><span> </span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span> </span><span class="annot"><span class="annottext">[color]
</span><span class="hs-identifier">_</span></span><span>         </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(color -&gt; Bool) -&gt; [color] -&gt; [color]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#filter"><span class="hs-identifier hs-var">filter</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621680943563"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943563"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">color -&gt; UniqSet color -&gt; Bool
forall a. Uniquable a =&gt; a -&gt; UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#elementOfUniqSet"><span class="hs-identifier hs-var">elementOfUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943563"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943568"><span class="hs-identifier hs-var">colors_ok_pref_nice</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-361"></span><span>                                        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; [color]
forall k cls color. Node k cls color -&gt; [color]
</span><a href="GHC.Data.Graph.Base.html#nodePreference"><span class="hs-identifier hs-var hs-var">nodePreference</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-362"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">color -&gt; Maybe color
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943564"><span class="hs-identifier hs-var">c</span></a></span><span>
</span><span id="line-363"></span><span>
</span><span id="line-364"></span><span>                </span><span class="hs-comment">-- we've got one of our preferences</span><span>
</span><span id="line-365"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; Bool -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; Bool
forall a. UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#isEmptyUniqSet"><span class="hs-identifier hs-var">isEmptyUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943571"><span class="hs-identifier hs-var">colors_ok_pref</span></a></span><span>
</span><span id="line-366"></span><span>                </span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943561"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943561"><span class="hs-identifier hs-var">c</span></a></span></span><span> </span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span> </span><span class="annot"><span class="annottext">[color]
</span><span class="hs-identifier">_</span></span><span>         </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(color -&gt; Bool) -&gt; [color] -&gt; [color]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#filter"><span class="hs-identifier hs-var">filter</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621680943560"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943560"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">color -&gt; UniqSet color -&gt; Bool
forall a. Uniquable a =&gt; a -&gt; UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#elementOfUniqSet"><span class="hs-identifier hs-var">elementOfUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943560"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943571"><span class="hs-identifier hs-var">colors_ok_pref</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-367"></span><span>                                        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node k cls color -&gt; [color]
forall k cls color. Node k cls color -&gt; [color]
</span><a href="GHC.Data.Graph.Base.html#nodePreference"><span class="hs-identifier hs-var hs-var">nodePreference</span></a></span><span> </span><span class="annot"><span class="annottext">Node k cls color
</span><a href="#local-6989586621680943600"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-368"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">color -&gt; Maybe color
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943561"><span class="hs-identifier hs-var">c</span></a></span><span>
</span><span id="line-369"></span><span>
</span><span id="line-370"></span><span>                </span><span class="hs-comment">-- it wasn't a preference, but it was still ok</span><span>
</span><span id="line-371"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; Bool -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; Bool
forall a. UniqSet a -&gt; Bool
</span><a href="GHC.Types.Unique.Set.html#isEmptyUniqSet"><span class="hs-identifier hs-var">isEmptyUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943573"><span class="hs-identifier hs-var">colors_ok</span></a></span><span>
</span><span id="line-372"></span><span>                </span><span class="hs-special">,</span><span> </span><span id="local-6989586621680943559"><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943559"><span class="hs-identifier hs-var">c</span></a></span></span><span> </span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span> </span><span class="annot"><span class="annottext">[color]
</span><span class="hs-identifier">_</span></span><span>         </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">UniqSet color -&gt; [color]
forall elt. UniqSet elt -&gt; [elt]
</span><a href="GHC.Types.Unique.Set.html#nonDetEltsUniqSet"><span class="hs-identifier hs-var">nonDetEltsUniqSet</span></a></span><span> </span><span class="annot"><span class="annottext">UniqSet color
</span><a href="#local-6989586621680943573"><span class="hs-identifier hs-var">colors_ok</span></a></span><span>
</span><span id="line-373"></span><span>                </span><span class="hs-comment">-- See Note [Unique Determinism and code generation]</span><span>
</span><span id="line-374"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">color -&gt; Maybe color
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="annot"><span class="annottext">color
</span><a href="#local-6989586621680943559"><span class="hs-identifier hs-var">c</span></a></span><span>
</span><span id="line-375"></span><span>
</span><span id="line-376"></span><span>                </span><span class="hs-comment">-- no colors were available for us this time.</span><span>
</span><span id="line-377"></span><span>                </span><span class="hs-comment">--      looks like we're going around the loop again..</span><span>
</span><span id="line-378"></span><span>                </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>
</span><span id="line-379"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe color
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>
</span><span id="line-380"></span><span>
</span><span id="line-381"></span><span>   </span><span class="hs-keyword">in</span><span>   </span><span class="annot"><span class="annottext">Maybe color
</span><a href="#local-6989586621680943565"><span class="hs-identifier hs-var">chooseColor</span></a></span><span>
</span><span id="line-382"></span><span>
</span><span id="line-383"></span><span>
</span><span id="line-384"></span><span>
</span><span id="line-385"></span></pre></body></html>